package cn.hesion.leetcode;
/**
 * ClassName: MaxSumRangeQuery <br/>
 * Description: <br/>
 * date: 2022/6/8 15:50<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1589. 所有排列中的最大和
 * @author: hesion
 * @create: 2022-06-08 15:50
 **/
public class MaxSumRangeQuery {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        Integer mod = 1000000007;
        int n = nums.length;
        int[] flag = new int[100010];
        int i=0;
        List<List<Long>> cnt = new ArrayList<List<Long>>();

        for(i=0;i<requests.length;++i ){
            int l = requests[i][0]+1;
            int r = requests[i][1]+1;

            if(l > n){
                continue;
            }

            if(r>n){
                r=n;
            }

            flag[l]++;
            flag[r+1]--;
        }
        long sum = 0;
        for(i = 1;i<=n;++i){
            sum += flag[i];
            List<Long> tmp = new ArrayList<Long>();
            tmp.add(sum);
            tmp.add((long)i);
            cnt.add(tmp);
        }
        cnt.sort((a,b)->{
            return (int) (a.get(0)-b.get(0));
        });
        Arrays.sort(nums);
        long ans = 0;
        for(i=0;i<n;++i){
            ans+=(cnt.get(i).get(0) * nums[i]) % mod;
            ans %= mod;
        }
        return (int)ans;
    }
}
